/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package learn.round1A;


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 *
 * @author robit
 */
public class NumberGame {

    NumberGame(){}

    private static Scanner s = null;
    private static PrintWriter o = null;

    final static int fib[]=new int[32];
    static {
        fib[0]=1;
        fib[1]=1;
        for(int i=2;i<32;i++)fib[i]=fib[i-1]+fib[i-2];
    }

        public static long reckon(){
        return reckon_1_1();
    }
        

    // passed !!!
    private static int reckon_0_0() {
        int A1=Int();
        int A2=Int();
        int B1=Int();
        int B2=Int();
        int count=0;
        int X1=A1,X2=A2,Y1=B1,Y2=B2;
        int x1=B1,x2=B2,y1=A1,y2=A2;
        int bound=max(A2,B2);
        for(int i=1;i<=bound;i++){
            for(int j=2*i;j<=bound;j++){
                int a=i,b=j;

                if(a>=X1&&a<=X2&&b>=Y1&&b<=Y2)count++;
                if(a>=x1&&a<=x2&&b>=y1&&b<=y2)count++;

                for(int k=0;fib[2*k+2]<=bound;k++){
                    a=(i*fib[2*k]+j*fib[2*k+1]);
                    b=(i*fib[2*k+1]+j*fib[2*k+2]);
                    if(a>=X1&&a<=X2&&b>=Y1&&b<=Y2)count++;
                    if(a>=x1&&a<=x2&&b>=y1&&b<=y2)count++;
                }
            }
        }

        return count;
    }

    // passed !!!
    private static long reckon_1_0() {
        int A1=Int();
        int A2=Int();
        int B1=Int();
        int B2=Int();
        long count=0;
        int X1=A1,X2=A2,Y1=B1,Y2=B2;
        int x1=B1,x2=B2,y1=A1,y2=A2;
        int bound=max(A2,B2);
        for(int i=1;i<=bound;i++){

            if(i>=X1&&i<=X2){
                int lb=max(2*i,Y1);
                count+=(lb<=Y2)?Y2-lb+1:0;
            }
            if(i>=x1&&i<=x2){
                int lb=max(2*i,y1);
                count+=(lb<=y2)?y2-lb+1:0;
            }

                for(int k=0;fib[2*k+1]*i<=bound;k++){
//                    a=(i*fib[2*k]+j*fib[2*k+1]);
//                    b=(i*fib[2*k+1]+j*fib[2*k+2]);
//                    if(a>=X1&&a<=X2&&b>=Y1&&b<=Y2)count++;
//                    if(a>=x1&&a<=x2&&b>=y1&&b<=y2)count++;
                      int _X1=X1-fib[2*k]*i,_X2=X2-fib[2*k]*i;
                      int _Y1=Y1-fib[2*k+1]*i,_Y2=Y2-fib[2*k+1]*i;
                      int lb=(int)Math.ceil((double)_X1/fib[2*k+1]);
                      int ub=(int)Math.floor((double)_X2/fib[2*k+1]);
                      lb=max(lb,(int)Math.ceil((double)_Y1/fib[2*k+2]));
                      ub=min(ub,(int)Math.floor((double)_Y2/fib[2*k+2]));
                      lb=max(lb,2*i);
                      count+=(lb<=ub)?ub-lb+1:0;

                      _X1=x1-fib[2*k]*i;_X2=x2-fib[2*k]*i;
                      _Y1=y1-fib[2*k+1]*i;_Y2=y2-fib[2*k+1]*i;
                      lb=(int)Math.ceil((double)_X1/fib[2*k+1]);
                      ub=(int)Math.floor((double)_X2/fib[2*k+1]);
                      lb=max(lb,(int)Math.ceil((double)_Y1/fib[2*k+2]));
                      ub=min(ub,(int)Math.floor((double)_Y2/fib[2*k+2]));
                      lb=max(lb,2*i);
                      count+=(lb<=ub)?ub-lb+1:0;


                }

        }

        return count;
    }

    // 8 secs small
    // 2 secs large
    public static long reckon_1_1(){
        final int A1=Int();
        final int A2=Int();
        final int B1=Int();
        final int B2=Int();
        class Tool{
            long count(int l,int r){
                int ubp=min(B2,r);
                int lbp=max(B1,l);
                return max(0,ubp-lbp+1);
            }
            boolean check(int a, int b){
                if(a==b)return false;
                if(b<a){
                    a=b+a; b=a-b;a=a-b;
                }
                if(b/a==1)return !check(b-a,a);
                return true;
            }
        };
        Tool t=new Tool();
        long count=0;
        int i,l,r;
        for(i=l=r=1;i<=A2;i++){
            while(t.check(l,i))l++;
            while(!t.check(r,i))r++;
            if(i>=A1)count+=t.count(1,l-1)+t.count(r,1000000);
        }
        return count;
    }
    



    /**
     * @param args the command line arguments
     */
    static boolean trig=false;
    public static void main(String[] args) throws IOException {
        // TODO code application logic here

        try {
            //String filename="test";
            String prob="C";
            //String filename=prob+"-small-practice";
            String filename=prob+"-large-practice";

            s = new Scanner(
                    new BufferedReader(new FileReader(filename+".in")));
            //s.useLocale(Locale.US);
            o = new PrintWriter(
                    new BufferedWriter(new FileWriter(filename+".out")));

            // Determine input line number
            int lineNums = s.nextInt();

            for (int i = 1; i <= lineNums; i++) {
                //if(i==8||i==9) continue;
                //if(i==10)trig=true;
                //println(""+i);
                o.println("Case #" + i + ": " + reckon());
            }
        } finally {
            s.close();
            o.close();
        }
    }


    private static int Int(){
        return s.nextInt();
    }
    private static long Long(){
        return s.nextLong();
    }
    private static String String(){
        return s.next();
    }
        private static void print(String str){
        System.out.print(str);
    }
    private static void println(String str){
        System.out.println(str);
    }
    private static int min(int a,int b){
        return Math.min(a,b);
    }
    private static int max(int a,int b){
        return Math.max(a,b);
    }

}
